//实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xⁿ ）。 
//
// 
//
// 示例 1： 
//
// 
//输入：x = 2.00000, n = 10
//输出：1024.00000
// 
//
// 示例 2： 
//
// 
//输入：x = 2.10000, n = 3
//输出：9.26100
// 
//
// 示例 3： 
//
// 
//输入：x = 2.00000, n = -2
//输出：0.25000
//解释：2-2 = 1/22 = 1/4 = 0.25
// 
//
// 
//
// 提示： 
//
// 
// -100.0 < x < 100.0 
// -231 <= n <= 231-1 
// -104 <= xⁿ <= 104 
// 
// Related Topics 递归 数学 👍 974 👎 0


package com.cjl.leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;

/**
 * [P50]_Pow(x, n)
 *
 * @author cjl
 * @date 2022-06-12 13:17:18
 */
public class P50_PowxN {
    public static void main(String[] args) {
        //测试代码
        Solution solution = new P50_PowxN().new Solution();
    }

    //力扣代码
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {

//        public double myPow(double x, int n) {
//            long N = n;
//            return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
//        }
//
//        public double quickMul(double x, long N) {
//            if (N == 0) {
//                return 1.0;
//            }
//            double y = quickMul(x, N / 2);
//            return N % 2 == 0 ? y * y : y * y * x;
//        }

        /**
         * 解题思路：递归；
         * 11: 6,3,1,1;
         * 14:7,4,2,1;
         * 31:16,8,4,2,1;
         *
         * @param x
         * @param n
         * @return
         */
        public double myPow(double x, int n) {
            if (n == 0) {
                return 1;
            }
            //处理边界问题，Integer.MIN_VALUE
            long N = n;
            return n > 0 ? pow(x, N) : 1.0 / pow(x, -N);
        }
        public double pow(double x, long n) {
            if (n == 0) {
                return 1.0;
            }
            if (n == 1) {
                return x;
            }
            double tmp = pow(x, n / 2);
            if (n % 2 == 1) {
                return tmp * tmp * x;
            }
            return tmp * tmp;

        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}